#include <QCoreApplication>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
class CinderellaGirls
{
public:
    int count(vector <int> talent, vector <int> skill)
    {
        int ans=0;
        vector<int> max_talent(talent),max_skill(skill);
        for(int i=0;i<talent.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(max_talent[j]<max_talent[i] && max_skill[j]<max_skill[i])
                {
                    max_talent[j]=0;
                    max_skill[j]=0;
                }
                if(max_talent[j]>max_talent[i] && max_skill[j]>max_skill[i])
                {
                    max_talent[i]=0;
                    max_skill[i]=0;
                }
            }
        }
        for(int i=0;i<talent.size();i++)
            if (max_talent[i]!=0) ++ans;
     return ans;
    }
};

class PAndPuns
{
public:
    string check(string text)
    {
        string cur;
        for(int i=0;i<text.size();i++)
        {
            cur.clear();
            cur.push_back(text[i]);
            cur.push_back(text[i+1]);
            for(int j=i+2;j<text.size()-1;j++)
            {
                if(text[j]==cur[0]&&text[j+1]==cur[1])
                    return "pun";
            }

        }

        return "not a pun";
    }

};
int currency[]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000};
set <int> currencyS(currency,currency+15);
int timesaa=0;
class NewBanknote
{
public:
    int num;
    vector <int> fewestPieces(int newBanknote, vector <int> amountsToPay)
    {
        vector<int> ans;
        currencyS.insert(newBanknote);
        for(vector<int>::iterator it = amountsToPay.begin();it!=amountsToPay.end();it++)
        {
            num=50;
            dfs(*it,0);
            ans.push_back(num);
 //           break;
        }
        return ans;
    }
    void dfs(int remainder,int floor)
    {
        cout<<++timesaa<<" "<<floor<<" "<<remainder<<"\n";
        if(remainder==0)
        {
            num=min(floor,num);
            return;
        }
        if(floor>50) return;
        set<int>::reverse_iterator it;
        for(it=currencyS.rbegin();it!=currencyS.rend();++it)
        {
            if((*it<=remainder && *it >=remainder/3)||(*it<remainder/2 && it == currencyS.crbegin()))
            {
                cout<<*it<<" ";
                dfs(remainder-*it,floor+1);
            }
        }

        return;
    }

};

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
//    vector <int> talent{46,70,39,53,10,47,73,95,95,27};
//    vector <int> skill{81,47,64,65,34,55,75,16,80,69};
//    PAndPuns test;
//    cout<<test.count(talent,skill);
//    cout<<test.check("aaab" );
    NewBanknote test;
    vector<int> amountsToPay={53, 9400, 9401, 30000};
    vector<int> aa;
    aa=test.fewestPieces(4700,amountsToPay);
    for(int i=0;i<aa.size();i++)
    {
        cout<<aa[i]<<" ";
    }
    return a.exec();
}
